package or;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class T0902 {
    char[] s;
    int[] memo;
    String[] digits;

    public int atMostNGivenDigitSet(String[] digits, int n) {
        s = Integer.toString(n).toCharArray();
        memo = new int[s.length];
        this.digits = digits;
        Arrays.fill(memo, -1);
        return dp(0, true, false)-1;
    }

    public int dp(int i, boolean isLimit, boolean isNum) {

        if (i == s.length) {
            return 1;
        }

        if (!isLimit && isNum && memo[i] != -1) {
            return memo[i];
        }
        int res = 0;
        if (!isNum) {
            res += dp(i + 1, false, false);
        }
        char up = isLimit ? s[i] : '9';
        for (String digit : digits) {
            char c = digit.charAt(0);
            if (digit.charAt(0) > up) break;
            res += dp(i + 1, isLimit && c == up, true);
        }
        if (!isLimit && isNum) {
            memo[i] = res;
        }
        return res;
    }

    @Test
    public void test() {

        String[] digits = {"1", "3", "5", "7"};
        System.out.println(atMostNGivenDigitSet(digits, 100));

    }
}
